function mergesort(arr, left, mid, right) {
    let tarr = [];
    let start = left;
    let k = 0;
    // 范围在[left, mid]
    // [mid+1, right]
    for (let i = mid + 1; left <= mid && i <= right; k++) {
        if (arr[left] < arr[i]) tarr[k] = arr[left++];
        else tarr[k] = arr[i++];
    }
    while (left <= mid) {
        tarr[k++] = arr[left++];
    }
    while (i <= right) {
        tarr[k++] = arr[i++];
    }
    for (let i = 0; i < k; i++) {
        arr[start++] = tarr[i];
    }
}

function mergeSort(arr, left, right) {
    let mid = Math.floor((left + right) / 2);
    if (left < right) {
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        mergesort(arr, left, mid, right);
    }
}


/**
 * 下面使用js数组方法来实现
 * @param {*} arr 
 * @returns 
 */

function mergeSortv2(arr = []) {
    let mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);
    if (arr.length < 2) return arr;
    return mergev2(mergeSortv2(left), mergeSortv2(right))
}

function mergev2(left = [], right = []) {
    let ans = [];
    let l = 0;
    let r = 0;
    while (l < left.length && r < right.length) {
        if (left[l] < right[r]) {
            ans.push(left[l++]);
        } else {
            ans.push(right[r++]);
        }
    }
    while (l < left.length) {
        ans.push(left[l++]);
    }
    while (r < right.length) {
        ans.push(right[r++]);
    }
    return ans;
}

console.log(mergeSortv2([11, 2, 5, 4, 34, 90, 22, 3, 1]));